package A.动态数组;

/**
 * 这是个好题！！！
 */
public class _53_最大子序列 {

    /**
     *贪心法--循环遍历 然后如果前面的总和小于0 那么久丢弃前面的序列从新技术
     * ---看题解思路自写代码
     */
    public int maxSubArray(int[] nums) {

        int max =nums[0];
        if (nums.length <=0){
            return 0;
        }else if (nums.length == 1){
            return nums[0];
        }else {
            int sum=nums[0];
            for (int i=0;i<nums.length;i++){
                if (sum <0){
                    sum=nums[i];
                    if (sum > max){
                        max = sum;
                    }
                }else {
                    sum += nums[i];
                    if (sum > max){
                        max = sum;
                    }
                }

            }
        }

        return max;

    }

    /**
     * 动态规划--从前往后遍历 前面数值>0 就加在目前的值上
     */
    public int maxSubArray1(int[] nums) {

        int max = nums[0];
        for (int i=1;i< nums.length;i++){
            if (nums[i-1] >0){
                nums[i] += nums[i-1];

            }else {
                nums[i] += nums[i-1];
            }
        }
        return max;

    }

    /**
     * 分治法 再说
     *
     */
}
